home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 2: CDPD 1 / Almathera Ten on Ten - Disc 2: CDPD 1.iso / pd / 076-100 / 092 / bawk / bawkpat.c < prev    next >
C/C++ Source or Header  |  1995-03-13  |  8KB  |  369 lines
  1. /*
  2.  * Bawk regular expression compiler/interpreter
  3.  */
  4. #include <stdio.h>
  5. #include "bawk.h"
  6.  
  7. int re_compile( patbuf )
  8. char    *patbuf;        /* where to put compiled pattern */
  9. {
  10.     /*
  11.      * Compile a regular expression from current input file
  12.      * into the given pattern buffer.
  13.      */
  14.     register int c,        /* Current character         */
  15.         o;        /* Temp                      */
  16.         register char delim,    /* pattern delimiter         */
  17.         *patptr,    /* destination string pntr   */
  18.         *lp,        /* Last pattern pointer      */
  19.         *spp;        /* Save beginning of pattern */
  20.     char *cclass();        /* Compile class routine     */
  21.  
  22.     DBUG_ENTER("re_compile");
  23.     lp = patptr = patbuf;
  24.     delim = getcharacter();
  25.  
  26.     while ( (c = getcharacter()) != -1 && c != delim )
  27.     {
  28.         /*
  29.          * STAR, PLUS and MINUS are special.
  30.          */
  31.         if (c == '*' || c == '+' || c == '-') {
  32.             if (patptr == patbuf ||
  33.                   (o=patptr[-1]) == BOL ||
  34.                   o == EOL ||
  35.                   o == STAR ||
  36.                   o == PLUS ||
  37.                   o == MINUS)
  38.                 error( "illegal occurrance op", RE_ERROR );
  39.             *patptr++ = ENDPAT;
  40.             *patptr++ = ENDPAT;
  41.             spp = patptr;        /* Save pattern end     */
  42.             while (--patptr > lp)    /* Move pattern down... */
  43.                 *patptr = patptr[-1];    /* one byte     */
  44.             *patptr =   (c == '*') ? STAR :
  45.                 (c == '-') ? MINUS : PLUS;
  46.             patptr = spp;        /* Restore pattern end  */
  47.             continue;
  48.         }
  49.         /*
  50.          * All the rest.
  51.          */
  52.         lp = patptr;            /* Remember start       */
  53.         switch(c) {
  54.  
  55.         case '^':
  56.             *patptr++ = BOL;
  57.             break;
  58.  
  59.         case '$':
  60.             *patptr++ = EOL;
  61.             break;
  62.  
  63.         case '.':
  64.             *patptr++ = ANY;
  65.             break;
  66.  
  67.         case '[':
  68.             patptr = cclass( patptr );
  69.             break;
  70.  
  71.         case ':':
  72.             if ( (c=getcharacter()) != -1 )
  73.             {
  74.                 switch( tolower( c ) )
  75.                 {
  76.  
  77.                 case 'a':
  78.                     *patptr++ = ALPHA;
  79.                     break;
  80.  
  81.                 case 'd':
  82.                     *patptr++ = DIGIT;
  83.                     break;
  84.  
  85.                 case 'n':
  86.                     *patptr++ = NALPHA;
  87.                     break;
  88.  
  89.                 case ' ':
  90.                     *patptr++ = PUNCT;
  91.                     break;
  92.  
  93.                 default:
  94.                     error( "unknown ':' type", RE_ERROR );
  95.  
  96.                 }
  97.             }
  98.             else
  99.                 error( "no ':' type", RE_ERROR );
  100.              break;
  101.  
  102.         case '\\':
  103.             c = getcharacter();
  104.  
  105.         default:
  106.             *patptr++ = CHAR;
  107.             *patptr++ = c;
  108.         }
  109.     }
  110.     *patptr++ = ENDPAT;
  111.     *patptr++ = 0;            /* Terminate string     */
  112.  
  113.     DBUG_EXECUTE("re_match",re_debug(patbuf,patptr););
  114.     DBUG_RETURN(patptr - patbuf);
  115. }
  116.  
  117. #ifndef DBUG_OFF
  118. re_debug(patbuf, patptr)
  119. register char *patbuf, *patptr;
  120. {
  121.     register char *lp;
  122.  
  123.     for ( lp=patbuf; lp<patptr; ++lp )
  124.     {
  125.         switch ( *lp )
  126.         {
  127.         case CHAR:    DBUG_PRINT("re_match",("char ")); break;
  128.         case BOL:    DBUG_PRINT("re_match",("bol ")); break;
  129.         case EOL:    DBUG_PRINT("re_match",("eol ")); break;
  130.         case ANY:    DBUG_PRINT("re_match",("any ")); break;
  131.         case CLASS:    DBUG_PRINT("re_match",("class(%d) ",*++lp)); break;
  132.         case NCLASS:    DBUG_PRINT("re_match",("notclass(%d) ",*++lp)); break;
  133.         case STAR:    DBUG_PRINT("re_match",("star ")); break;
  134.         case PLUS:    DBUG_PRINT("re_match",("plus ")); break;
  135.         case MINUS:    DBUG_PRINT("re_match",("minus ")); break;
  136.         case ALPHA:    DBUG_PRINT("re_match",("alpha ")); break;
  137.         case DIGIT:    DBUG_PRINT("re_match",("digit ")); break;
  138.         case NALPHA:    DBUG_PRINT("re_match",("notalpha ")); break;
  139.         case PUNCT:    DBUG_PRINT("re_match",("punct ")); break;
  140.         case RANGE:    DBUG_PRINT("re_match",("range ")); break;
  141.         case ENDPAT:    DBUG_PRINT("re_match",("endpat ")); break;
  142.         default:    DBUG_PRINT("re_match",("<%c> ", *lp)); break;
  143.         }
  144.     }
  145. }
  146. #endif
  147.  
  148. char *
  149. cclass( patbuf )
  150. register char    *patbuf;    /* destination pattern buffer */
  151. {
  152.     /*
  153.      * Compile a class (within [])
  154.      */
  155.     register char *patptr,    /* destination pattern pointer */
  156.         *cp;        /* Pattern start     */
  157.     register int c,        /* Current character */
  158.         o;        /* Temp              */
  159.  
  160.     DBUG_ENTER("cclass");
  161.     patptr = patbuf;
  162.  
  163.     if ( (c = getcharacter()) == -1 )
  164.         error( "class terminates badly", RE_ERROR );
  165.     else if ( c == '^')
  166.     {
  167.         /*
  168.          * Class exclusion, for example: [^abc]
  169.          * Swallow the "^" and set token type to class exclusion.
  170.          */
  171.         o = NCLASS;
  172.     }
  173.     else
  174.     {
  175.         /*
  176.          * Normal class, for example: [abc]
  177.          * push back the character and set token type to class
  178.          */
  179.         ungetcharacter( (char) c );
  180.         o = CLASS;
  181.     }
  182.     *patptr++ = o;
  183.  
  184.     cp = patptr;    /* remember where byte count is */
  185.     *patptr++ = 0;    /* and initialize byte count */
  186.     while ( (c = getcharacter()) != -1 && c!=']' )
  187.     {
  188.         o = getcharacter();        /* peek at next char */
  189.         if (c == '\\')            /* Store quoted chars */
  190.         {
  191.             if ( o == -1) /* Gotta get something */
  192.                 error( "class terminates badly", RE_ERROR );
  193.             *patptr++ = o;
  194.         }
  195.         else if ( c=='-' && (patptr-cp)>1 && o!=']' && o != -1 )
  196.         {
  197.             c = patptr[-1];        /* Range start     */
  198.             patptr[-1] = RANGE;    /* Range signal    */
  199.             *patptr++ = c;        /* Re-store start  */
  200.             *patptr++ = o;        /* Store end char  */
  201.         }
  202.         else
  203.         {
  204.             *patptr++ = c;        /* Store normal char */
  205.             ungetcharacter( (char) o );
  206.         }
  207.     }
  208.     if (c != ']')
  209.         error( "unterminated class", RE_ERROR );
  210.     if ( (c = (patptr - cp)) >= 256 )
  211.         error( "class too large", RE_ERROR );
  212.     if ( c == 0 )
  213.         error( "empty class", RE_ERROR );
  214.     *cp = c;        /* fill in byte count */
  215.  
  216.     DBUG_RETURN(patptr);
  217. }
  218.  
  219. int match( line, pattern )
  220. char    *line;        /* line to match */
  221. register char *pattern;    /* pattern to match */
  222. {
  223.     /*
  224.      * Match the current line (in Linebuf[]), return 1 if it does.
  225.      */
  226.     register char *l;    /* Line pointer       */
  227.     char    *pmatch();
  228.     register char *next;
  229.     register int    matches;
  230.  
  231.     DBUG_ENTER("match");
  232.     matches = 0;
  233.     for (l = line; *l; l++)
  234.     {
  235.         if ( next = pmatch(line, l, pattern) )
  236.         {
  237.             l = next - 1;
  238.             ++matches;
  239.             DBUG_PRINT("match",("match found"));
  240.         }
  241.     }
  242.  
  243.     DBUG_RETURN(matches);
  244. }
  245.  
  246. char *
  247. pmatch(linestart, line, pattern)
  248. char    *linestart;     /* start of line to match */
  249. char    *line;         /* (partial) line to match      */
  250. char    *pattern;     /* (partial) pattern to match   */
  251. {
  252.     register char *l;/* Current line pointer         */
  253.     register char *p;/* Current pattern pointer      */
  254.     register char c; /* Current character            */
  255.     register char *e;/* End for STAR and PLUS match  */
  256.     register int op; /* Pattern operation            */
  257.     register int n;     /* Class counter                */
  258.     char    *are;     /* Start of STAR match          */
  259.  
  260.     DBUG_ENTER("pmatch");
  261.     l = line;
  262.  
  263.     DBUG_PRINT("pmatch",("line: (%s)", line));
  264.  
  265.     p = pattern;
  266.     while ((op = *p++) != ENDPAT) {
  267.  
  268.     DBUG_PRINT("pmatch",("byte[%d] = 0%o, '%c', op = 0%o",l-line, *l, *l, op));
  269.  
  270.         switch(op) {
  271.  
  272.         case CHAR:
  273.             if ( *l++ != *p++)
  274.                 DBUG_RETURN(0);
  275.             break;
  276.  
  277.         case BOL:
  278.             if (l != linestart)
  279.                 DBUG_RETURN(0);
  280.             break;
  281.  
  282.         case EOL:
  283.             if (*l != '\0')
  284.                 DBUG_RETURN(0);
  285.             break;
  286.  
  287.         case ANY:
  288.             if (*l++ == '\0')
  289.                 DBUG_RETURN(0);
  290.             break;
  291.  
  292.         case DIGIT:
  293.             if ((c = *l++) < '0' || (c > '9'))
  294.                 DBUG_RETURN(0);
  295.             break;
  296.  
  297.         case ALPHA:
  298.             c = *l++;
  299.             c = tolower( c );
  300.             if (c < 'a' || c > 'z')
  301.                 DBUG_RETURN(0);
  302.             break;
  303.  
  304.         case NALPHA:
  305.             c = *l++;
  306.             c = tolower( c );
  307.             if (c >= 'a' && c <= 'z')
  308.                 break;
  309.             else if (c < '0' || c > '9')
  310.                 DBUG_RETURN(0);
  311.             break;
  312.  
  313.         case PUNCT:
  314.             c = *l++;
  315.             if (c == 0 || c > ' ')
  316.                 DBUG_RETURN(0);
  317.             break;
  318.  
  319.         case CLASS:
  320.         case NCLASS:
  321.             c = *l++;
  322.             n = *p++ & 0377;
  323.             do {
  324.                 if (*p == RANGE) {
  325.                     p += 3;
  326.                     n -= 2;
  327.                     if (c >= p[-2] && c <= p[-1])
  328.                         break;
  329.                 }
  330.                 else if (c == *p++)
  331.                     break;
  332.             } while (--n > 1);
  333.             if ((op == CLASS) == (n <= 1))
  334.                 DBUG_RETURN(0);
  335.             if (op == CLASS)
  336.                 p += n - 2;
  337.             break;
  338.  
  339.         case MINUS:
  340.             e = pmatch(linestart,l,p);/* Look for a match    */
  341.             while (*p++ != ENDPAT);    /* Skip over pattern   */
  342.             if (e)            /* Got a match?        */
  343.                 l = e;        /* Yes, update string  */
  344.             break;            /* Always succeeds     */
  345.  
  346.         case PLUS:            /* One or more ...     */
  347.             if ((l = pmatch(linestart,l,p)) == 0)
  348.                 DBUG_RETURN(0);    /* Gotta have a match  */
  349.         case STAR:            /* Zero or more ...    */
  350.             are = l;        /* Remember line start */
  351.             while (*l && (e = pmatch(linestart,l,p)))
  352.                 l = e;        /* Get longest match   */
  353.             while (*p++ != ENDPAT);    /* Skip over pattern   */
  354.             while (l >= are) {    /* Try to match rest   */
  355.                 if (e = pmatch(linestart,l,p))
  356.                     DBUG_RETURN(e);
  357.                 --l;        /* Nope, try earlier   */
  358.             }
  359.             DBUG_RETURN(0);        /* Nothing else worked */
  360.  
  361.         default:
  362.             fprintf( stderr, "bad op code %d\n", op );
  363.             error( "can't happen -- match", RE_ERROR );
  364.         }
  365.     }
  366.     DBUG_RETURN(l);
  367. }
  368.  
  369.